package com.lwl.Algorithmic_data_structure.快排.mycode;

/**
 * 快速排序的递归版本
 *
 * leftSide,rightSide边界的意义可以理解为作为下标的leftSide对应的元素必须是符合范围的要求，下一个就不一定了（因为还没观察到，rightSide同理相反）
 */
public class QuickSortRecursive {
    
    public static void main(String[] args) {
        // 0 ~ 10 --> （0，10）
//        System.out.println(Math.random() * 10);

        int[] array = {
            1,2,4,5,6,1,2,3,5,3,1,6,5,6,9,3
//                7,8,4,2,5,5,2,5,4,6,5,5,6,6,3,5,2,1,4,4,6,6,5,2,4,3,5,2,4,4,8,8,7,4,5,6,1,2,3,4,5
        };
//        int[] equalArea = partition(array, 0, array.length - 1);
//        for (int i = 0; i < array.length; i++) {
//            System.out.print(array[i] + " ");
//        }
//        System.out.println();
//        System.out.println(equalArea[0] + "," + equalArea[1]);

    }

    public static void quickSortRecursive(int[] array)
    {
        if (array == null || array.length <= 1)
        {
            return ;
        }
        process(array, 0, array.length - 1);
    }

    private static void process(int[] array, int left, int right) {

        if (left >= right)
        {
            return;
        }
        // 随机选一个划分值置换到当前数组最后的位置上
        int partitionIndex = left + (int)(Math.random() * (right - left + 1));
        Partition.swap(array,partitionIndex,right);

        int[] equalArea = Partition.partition(array,left,right);

        process(array,left,equalArea[0] - 1);
        process(array,equalArea[1] + 1,right);
    }
}
